---
tags:
  - CN
  - computer-network
---
# 基本概念
> 此处仅讨论比特差错(1<->0)
1. 分类 -> 检错编码和纠错编码
2. 码距(海明距离) -> **两个码字**在对应位置上取值不同的比特数量
        -> 可以通过异或运算得到新的码, 新的码中1的位数即为码距
3. 编码集的码距 -> 任意两个有效码字之间码距的最小值
4. 差错控制理论 -> 编码方案的检错能力与纠错能力与码距l的关系为$$l=d+c+1,且d\geq c$$其中, d为检错位数, c为纠错位数, 纠错能力不超过检错能力, 因此有边界条件c=0以及d=c
# 检错编码
> 冗余编码技术, 在信息位(有效数据)发送前, 按照特定规则附加冗余位(检验位), 确保码数符合规则再发送; 接收方使用同样规则来校验
## 奇偶检验码
1. 奇检验码 -> 附加检验位后, 码字中1的位数为奇数
2. 偶检验码 -> 附加检验位后, 码字中1的位数为偶数
> 只能检测奇数位错误
## 循环冗余码
   -> Cyclic Redundancy Code, CRC
1. 生成多项式(G(x)对应二进制码) 
    阶数为最高项次数r, 最多有r+1项, 最高位和最低位必须为0
2. 用信息位计算, 生成冗余校验信息(帧检验序列,FCS)
    计算方式为模2除法(本质上是吧竖式除法换成异或)
3. 附加在原始数据(信息位)之后
4. 接收方使用相同的模二触发检验, 为0则认为传输无差错, 否则重传/丢弃
> 在工程实践中常认为, 被数据链路层接受的帧, 几乎可以确定在传输中为发生差错
# 纠错编码
- 最常见的纠错码 -> 海明码
- 信息位n位和检验位k位按一定规则排列
- 每个校验位对应一个校验组(通常采用偶校验), 从而实现检测甚至确定错误位置实现单比特纠错
## 海明码的构造
1. 确定总位数(n,k满足)$$2^{k}\geq n+k+1$$通过代值即可求k
2. 检验位放在海明码的$2^{i-1}$位置上(海明码按照1~n+k的下标排列, 可以从小到大或者反过来)
3. 分组检验 -> 将每一个信息位的海明位号进行换算成二进制, 需要用到二进制为1的位对应的检验位来检验(海明码位也是对应的)
4. 检验位取值 -> 相同检验位分为同一组, 同一组异或计算得到检验位取值
## 海明码的纠错
1. 同一分组(包括检验位)共同计算异或得到当前分组的检测值, 如果为0则正确
2. 多个分组拼起来成为0或者错误位的序号
3. 一般来说, 开始有一位奇偶校验用于确定有奇数位错还是有偶数位错, 来纠错或者重传

# 总结
1. 注意**码距**的相关概念